n^2 배열 자르기

문제 설명

정수 n,left,right 가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n 행 n 열 크기의 비어있는 2차원 배열을 만듭니다.
2. i=1,2,3,..., n 에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i 행 i 열까지의 영역 내의 모든 빈칸을 숫자 i 로 채웁니다.
3. 1행,2행 …, n 행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr 이라 할 때, arr[left],arr[left+1],…,arr[right]만 남기고 나머지는 지웁니다. 정수 n, left,right, 가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• $1<=n<=10^7$
• $0<=left<=right<n^2$
• $right-left<10^5$

입출력 예

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

입출력 예 설명

1번 예시

2번 예시

풀이

첫번째 접근

• brute-force 로 쉽게 접근 가능해보여서 단순하게접근
• 리스트를 n 루프를 두번 반복하여 요소에 번호를 부여

def solution(n,left,right):
	answer=[j+1 if j>i else i+1 for j in range(n) for i in range(n)]
	return answer[left:right+1]

Fail

시간 초과로 인한 실패

실패의 이유는 무엇인가?

• 제약조건에서 $n$ 의 크기가 $n^7$ 인것을 봤을때 for 문을 두번 돌린다는것은 총 $n^{14}$ 의 연산이 필요하기 때문에 시간 제약에 걸린다.

어떻게 해결할 것인가?

모든 요소를 하나하나 개산하지 않는 방식이 필요하다. 완전탐색 보다는 수학적인 접근이 필요해 보인다.

메모리를 사용하여 접근할 수 없고 어떤 방법을 쓰더라도 코드로 해결이 될 수 없어 보인다.

두번째 접근

[! question] 규칙을 알 수 없을까? 행렬을 보면 nxn 의 정사각 형 행렬이다. 행 혹은 열의 순서 값보다 리스트 안의 원소가 작다면 행 혹은 열의 순서로 덮어 씌워진다. 만약 행렬을 만들지 않고 하나의 배열을 만들어 몇번째 요소가 이차열 배열 상 몇번째 열 몇번째 항인지 파악할 수 있다면 루프를 두번 돌 필요 없이 해결 가능할 것이다. 특정 요소의 행과 열을 구하고 큰값을 찾으면 원하는 리스트를 구할 수 있다.

print([i//n for i in range(n*n)]) # i 를 n 으로 나눈 몫을 확인하면 몇번째 열인지 파악이 가능하다. 다만 인덱스 기준 이기때문에 +1 을 해줘야 한다.
print([i%n for i in range(n*n)]) # i 를 n 으로 나눈 나머지를 확인하면 몇번째 행인지 파악이 가능하다. 이 경우에도 인덱스 기준이기 때문에 +1 을 해줘야 한다.

풀이

def solution(n,left,right):
	return [max(i//n,i%n)+1 for i in range(left,right+1)]